package com.kevinkk.greedy;

import java.util.Arrays;

/**
 * 给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组:
 * 选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。
 * 重复这个过程恰好 k 次。可以多次选择同一个下标 i 。
 * 以这种方式修改数组后，返回数组 可能的最大和 。
 */

public class MaximizeSumOfArrayAfterKNegations {
    class Solution {
        public int largestSumAfterKNegations(int[] nums, int k) {
            Arrays.sort(nums);
            for (int j = 0; j < nums.length; j++) {
                // 只修改 负数
                if (nums[j] < 0 && k > 0) {
                    nums[j] = -nums[j]; // 修改数组元素
                    k--;
                }
            }

            // 修改之后如果还有剩余，则重新修改最小的正数
            if (k % 2 == 1) {
                Arrays.sort(nums);
                nums[0] *= -1;
            }

            int res = 0;
            for (int i : nums)
                res += i;

            return res;
        }
    }
}
